#include <stdio.h>
#include "malloc.h"
#include "stdbool.h"
typedef  char dataType;
//定义树的类型
typedef  struct TreeNode{
    dataType  data;  //结点存储数据
    struct  TreeNode  * Lchild;  //指向左结点的指针
    struct  TreeNode * Rchild; //指向又结点的指针
}TreeNode,*Tree; // Tree 结构体指针类型 用于定义指向结点的指针
//创建树的新节点的函数
//功能：为新结点分配内存、初始化数据和指针，返回新节点的地址
TreeNode* createNode(dataType n){
    //1、分配内存
    TreeNode * newNode=(TreeNode *)malloc(sizeof (TreeNode));
    if(newNode==NULL){
        printf("分配内存失败");
        return NULL;
    }
    //2、、初始化数据和指针
    newNode->data=n;
    newNode->Lchild=NULL;
    newNode->Rchild=NULL;
    //3、返回新节点的地址
    return newNode;
}
//先序遍历（根左右）//递归
void preOrder(Tree T){
    if(T!=NULL){
        printf("%c  ",T->data);
        preOrder(T->Lchild);
        preOrder(T->Rchild);
    }
}
//后序遍历  左右根
void postOrder(Tree T){
    if(T!=NULL){
        postOrder(T->Lchild);
        postOrder(T->Rchild);
        printf("%c  ",T->data);
    }
}
//非递归中序遍历
// 栈中元素类型改为 TreeNode*（而非 char），才能通过指针访问子节点
typedef TreeNode* EleType;

// 定义栈的结构
typedef struct {
    EleType* data;     // 指向存储节点指针的数组（修正：元素类型为 TreeNode*）
    int top;           // 栈顶索引（-1 表示空栈）
    int capacity;      // 栈的最大容量
} SeqStack; // 修正：结构体名拼写（SeqSack→SeqStack）

// 初始化栈
void init(SeqStack* p) {
    if (p == NULL) {
        printf("初始化失败，参数无效\n");
        return; // 修正：添加返回，避免后续操作空指针
    }
    // 初始容量设为 4（可根据需求调整）
    p->capacity = 4;
    p->data = (EleType*)malloc(sizeof(EleType) * p->capacity);
    if (p->data == NULL) {
        printf("栈内存分配失败\n");
        return;
    }
    p->top = -1; // 栈空时 top 为 -1
}

// 入栈（存储节点指针）
void pushStack(SeqStack* p, EleType node) {
    if (p == NULL || node == NULL) {
        printf("入栈失败，参数无效\n");
        return;
    }
    // 栈满时扩容（2 倍扩容）
    if (p->top == p->capacity - 1) { // 修正：栈满条件（top 指向最后一个元素，索引为 capacity-1）
        EleType* temp = (EleType*)realloc(p->data, sizeof(EleType) * p->capacity * 2);
        if (temp == NULL) {
            printf("栈扩容失败\n");
            return;
        }
        p->data = temp;
        p->capacity *= 2;
        printf("栈扩容成功，新容量：%d\n", p->capacity);
    }
    p->top++;
    p->data[p->top] = node; // 入栈：存储节点指针
}

// 判断栈是否为空
bool isEmpty(SeqStack* p) {
    return (p != NULL) && (p->top == -1);
}

// 出栈（返回节点指针）
EleType popStack(SeqStack* p) { // 修正：函数名更清晰（del→popStack）
    if (p == NULL || isEmpty(p)) {
        printf("出栈失败，栈为空\n");
        return NULL; // 栈空时返回 NULL
    }
    return p->data[p->top--]; // 出栈并移动栈顶
}


// -------------------------- 非递归中序遍历（修正核心逻辑） --------------------------
// 思路：栈存储节点指针，先压左子树，弹出时访问节点，再处理右子树
void inOrder(Tree T) { // 修正：函数名更清晰（in→inOrder）
    if (T == NULL) {
        printf("树为空，无需遍历\n");
        return;
    }

    SeqStack stack;
    init(&stack);
    TreeNode* current = T; // 当前遍历的节点指针

    while (current != NULL || !isEmpty(&stack)) {
        // 1. 将当前节点及所有左子节点依次入栈
        while (current != NULL) {
            pushStack(&stack, current); // 入栈节点指针（而非数据）
            current = current->Lchild;  // 继续向左遍历
        }

        // 2. 栈不为空时，弹出栈顶节点（左子树遍历完毕）
        current = popStack(&stack);
        printf("%c  ", current->data); // 访问当前节点的数据

        // 3. 遍历当前节点的右子树
        current = current->Rchild;
    }
}

//Levelorde 按层输出  实现思路   队列
void Levelorde(Tree T){
    Tree temp;
    //临时队列
    Tree Quenue[1000];
    int  front=0,rear=0;
    if(T==NULL) return;
    //2\初始化队列
    Quenue[rear++]=T;
    //3、循环处理队列中的结点，直到队列为空
    while(front<rear){
        //出队操作,
        temp=Quenue[front++];
        //访问当前结点
        printf("%c  ",temp->data);
        if(temp->Lchild){
            Quenue[rear++]=temp->Lchild;
        }
        if(temp->Rchild){
            Quenue[rear++]=temp->Rchild;
        }
    }
}
int main() {
//    构建二叉树
//1、创建结点
TreeNode  *node1= createNode('A');
TreeNode  *node2= createNode('B');
TreeNode  *node3= createNode('C');
TreeNode  *node4= createNode('D');
TreeNode  *node5= createNode('E');
//2、构建二叉树的结构（通过指针关联结点，形成树形结构）
node1->Lchild=node2;
node1->Rchild=node3;
node2->Lchild=node4;
node2->Rchild=node5;
//中序遍历
    printf("----------------中序遍历结果-----------------、\n");
//    inOrder(node1);
    printf("\n");
    printf("----------------先序遍历结果-----------------、\n");
    preOrder(node1);
    printf("\n");
    printf("----------------后序遍历结果-----------------、\n");
    postOrder(node1);
    printf("\n");
    Levelorde(node1);
  return 0;
}

